class LRUCache {
    public class Node{
        int key;
        int val;

        Node next;
        Node prev;

        Node(int key,int val) {
            this.key = key;
            this.val = val;
        }
    }

    public Node head;
    public Node tail;
    public Map<Integer,Node> map;
    public int n;

    public LRUCache(int capacity) {
        head = new Node(-1,-1);
        tail = new Node(-1,-1);
        head.next = tail;
        tail.prev = head;
        map = new HashMap<>();
        n = capacity;
    }
   
            public int get(int key) {
        if(map.containsKey(key)) {
            Node node = map.get(key);
            refresh(node);
            return node.val;
        }

        return -1;
    }
   
            public void put(int key, int value) {
        Node node = null;
        if(map.containsKey(key)) {
            node = map.get(key);
            node.val = value;
        } else {
            if(n == map.size()) {
                //删除链表头的元素
                Node cur = tail.prev;
                delete(cur);
                map.remove(cur.key);//这里得链表头的元素
            }
            node = new Node(key,value);
            map.put(key,node);
        }
        refresh(node);
    }

    private void refresh(Node node) {
        delete(node);

        //放到链表头
        Node Hnext = head.next;

        node.next = Hnext;
        Hnext.prev = node;
        head.next = node;
        node.prev = head;
    }

    //删除指定的节点
            private void delete(Node node) {
        Node Nnode = node.next;

        if(node.prev != null) {
            node.prev.next = Nnode;
            Nnode.prev = node.prev;
        }
        
    }
}

/**
  * Your LRUCache object will be instantiated and called as such:
  * LRUCache obj = new LRUCache(capacity);
  * int param_1 = obj.get(key);
  * obj.put(key,value);
  */